Vertex Cover:
Data Structure: 
n: number of vertices
m[1..n][1..n]: Adjacency matrix, 
B: number giving target length of dominating set

Length
O(n^2) elements
We don’t need the exact number. We just need a polynomially-related estimate.

Witness
w: Finite but unbounded list of labels for vertices.
Note that this structure will be stored on the left  of our Turing machine’s tape by the oracle. In our model, our verification algorithm must treat this as an essentially random string of symbols from the tape alphabet we will assume that all such strings will map to some instance of our witness data structure in an efficient (read: polynomial time) manner, and that there is an oracle string for every instance of our witness data structure.
In short, just give a simple data structure and let the oracle fill in the fields. Do not put any preconditions on the witness, such as “the length of the set is less than k.” If the oracle does too much work, we could have a polynomial verification algorithm for a problem that is not NP!
One loophole to that: you can put a limit on the sizes of arrays and such if you are willing to treat any additional data generated by the oracle as garbage that does not affect whether or not the witness is for a yes instance. For instance, here, your could let your witness be an array W’[1..n] of n booleans indicating whether a given vertex is in the dominating set: W’[n+1] could be safely ignored. You would still need to count the number of vertices and compare that with k, however. 
(Don’t write these last few italicized paragraphs on homework or a test, please!)

Verification Algorithm
The verification algorithm for a non-deterministic Turing machine must always return “true” for yes instances and, for a no instance it can return false, or it can hang, but it must never return true.
For our purposes, the verification algorithm must be polynomial for yes instances: for no instances, it can even enter an infinite loop, as mentioned above.
1.	procedure verify( m, B, w ) 
2.		if( |w| > B ) return false
3.		foreach x in w
4.			for i = 1 to n 
5.				m[i][x] = m[x][i] = 0; /* Remove all edges incident with x. */	
6.		for i = 1 to n
7.			for j = 1 to n
8.				if (m[i][j] == 1 ) return false; /* Some edge wasn’t covered. */
9.		return true

Analysis:
Assume a yes instance, as implied above.
Note, for ease of analysis we can assume that this algorithm is executed on a RAM machine: if it is polynomial on a RAM machine, it is polynomial on a Turing machine.
Assume |w| <= B <= n.
Then, the loop at line 3 will be executed O(n) times.
The loop at line 4 will be executed n times, and a constant amount of instructions is executed during each iteration.
Thus, the running time for the loop at line 3 is O(n).
The loop at line 6 is executed n times, as is the loop at line 7. Again, a constant amount of instructions is executed for each iteration of the loop at line 7. The running time for the loop at line 6 is O(n^2), and the total running time is also O(n^2), which is polynomial Q.E.D.

Subset sum
Data structure
s[1..n]: List of numbers
B: target sum
Length
n+1 numbers
Witness
w: Finite but unbounded list of indices

Verification algorithm
Assume that an out-of-bounds access to s will lead to an infinite loop.
function verify (s, B, w ) 
	sum <- 0
	foreach i in w
		sum <- sum + w[i]
	return ( sum == B )

Analysis
Again, we only look at yes instances. Thus, length(w) <=n. the for loop executes a constant amount of instructions for each i in w and the remaining instructions are trivial (we can assume a RAM model for performance analysis); thus the algorithm is O(n).